CPSC 461 Labs 2&3 Indexing Review Part 1

	Indexing Review Part 1

	The following review questions were covered in Labs 02 and 03 and are questions taken from the course website. NOT ALL questions from the course website were discussed in lab. Please note that the information presented here does not necessarily represent a complete answer to the review question. The information is intended to spark student's memory for those who attended lab OR provide a base (hint) from where to start for those students who did not attend lab.

	Question 1: What is the best placement strategy to use for re-using entries in the free-list of a fixed length record file? WHY?
		First Fit. Since all records are of fixed length, the first available entry in the free-list will be large enough to fit a new record.

	Question 2: Explain how compaction affects internal and external fragmentation within a file?
		Compaction will eliminate external fragmentation and will not affect internal fragmentation.

	Question 3: What is the usual measure of efficiency for large file sorts?
		Time Complexity. A comparison of sorting algorithms will normally consider both the number of data swaps and the number of comparisons required.

	Question 4: What are the four characteristics of an ideal primary key in an indexed file?
		unique, canonical, dataless, unmodifiable

	Question 5: Suppose we had a dynamic, indexed, fixed length record file and we wanted to avoid having to maintain a free list. How coul we make sure that there would be no wasted space within the file?
		ADDING A RECORD - add to the end of the file, update the index DELETING A RECORD - delete the record, move the last record to the deleted records location, update the index file

	Question 6: One of the fields in the records structure of a large, varying length record file contains text values that vary in length from 2 to 256 bytes. Their average length is 30 bytes. Describe how you would design this field of the record and why?
		CASE 1 - fixed length field, this makes managing and maintaining the record file uncomplicated but wastes a lot of space CASE 2 - varying length field, this uses space efficiently but makes managing and maintaining the record file somewhat more complicated CASE 3 - a combination (fixed length field that points to a space in memory where the data is kept), this tries to capitalize on the advantages of both approaches listed above but does imply the creation of a new 'file/memory space' to store the varying length data


BACK

Questions? Please Email: gwen@cpsc.ucalgary.ca

Last modified October 7, 2002